﻿#pragma once
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>

using namespace std;
#define MaxVertexNum 16384 /* 最大顶点数设为100 */
typedef int Vertex;		   /* 用顶点下标表示顶点,为整型 */
typedef double WeightType; /* 边的权值设为整型 */
typedef int DataType;	   /* 顶点存储的数据类型设为字符型 */

typedef struct ENode* PtrToENode;
struct ENode
{
    Vertex V1, V2;	   /* 有向边<V1, V2> */
    WeightType Weight; /* 权重 */
};
typedef PtrToENode Edgem;

/* 邻接点的定义 */
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{
    Vertex AdjV;		/* 邻接点下标 */
    WeightType Weight;	/* 边权重 */
    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode
{
    PtrToAdjVNode FirstEdge; /* 边表头指针 */
    DataType Data;			 /* 存顶点的数据 */
                             /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];	 /* AdjList是邻接表类型 */

/* 图结点的定义 */
typedef struct GNode* PtrToGNode;
struct GNode
{
    int Nv;	   /* 顶点数 */
    int Ne;	   /* 边数   */
    AdjList G; /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */


void Visit(Vertex V);
void InitVisited();
void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex));
Vertex listDFS(LGraph Graph, void (*Visit)(Vertex));
int BFS(LGraph Graph, Vertex V, void (*Visit)(Vertex));
void DFSListComponents(LGraph Graph, void (*Visit)(Vertex));
